/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
    // 答案必然在 1 到 nums.length+1 之间
    let len = nums.length,
        idx = 0
    // 整理思路：1放在下标0，2放在下标1，i放在下标i+1
    // 若下标0对应数字为k，则把k放到下标k-1的地方，原本下标k-1对应的数字放到下标0，循环检查直到下标0对应的数字为1或者越界（负数 和 超过长度大小）
    while (idx < len) {
        // 负数 和 超过长度大小 的置为-1
        if (nums[idx] <= 0 || nums[idx] > len) {
            nums[idx] = -1
            idx++
        } else {
            // idx++
            if (nums[idx] == nums[nums[idx] - 1]) {
                // 位置正确跳过
                idx++
            } else {
                // 交换
                let temp1 = nums[idx]
                let temp2 = nums[nums[idx] - 1]
                nums[nums[idx] - 1] = temp1
                nums[idx] = temp2
                // 交换完继续检查当前位（交换来的新值）的位置是否正确
            }
        }
    }

    // 找到第一个没有归位的数
    for (let i = 0; i < len; i++) {
        if (nums[i] != i + 1) {
            return i + 1
        }
    }

    // 否则返回 长度+1
    return len + 1
}
